package acm.pta;

import acm.第二轮.H;

import java.util.*;

public class T14_2 {
    static int N, M, K, DS;
    static int[][] G;
    static int[] d;
    static boolean[] vis;
    static final int INF = 1000000000;

    public static String fun(int n,int m,int k,int limit,String[] src,String[] target,Integer[] weight) {
//        Scanner in = new Scanner(System.in);
        N = n;
        M = m;
        K = k;
        DS = limit;
        G = new int[N + M + 1][N + M + 1];
        d = new int[N + M + 1];
        vis = new boolean[N + M + 1];
        for (int i = 0; i < N + M + 1; i++) {
            Arrays.fill(G[i], INF);
            G[i][i] = 0;
        }
        for (int i = 0; i < K; i++) {
            String s1 = src[i];
            String s2 = target[i];
            int v1 = s1.charAt(0) == 'G' ? Integer.parseInt(s1.substring(1)) + N : Integer.parseInt(s1);
            int v2 = s2.charAt(0) == 'G' ? Integer.parseInt(s2.substring(1)) + N : Integer.parseInt(s2);
            int dist = weight[i];
            G[v1][v2] = G[v2][v1] = dist;
        }
        int ansId = -1;
        double ansDis = -1, ansAvg = INF;
        for (int i = N + 1; i <= N + M; i++) {
            double minDis = INF, avg = 0;
            Dijkstra(i);
            for (int j = 1; j <= N; j++) {
                if (d[j] > DS) {
                    minDis = -1;
                    break;
                }
                if (d[j] < minDis) minDis = d[j];
                avg += 1.0 * d[j] / N;
            }
            if (minDis == -1) continue;
            if (minDis > ansDis) {
                ansId = i;
                ansDis = minDis;
                ansAvg = avg;
            } else if (minDis == ansDis && avg < ansAvg) {
                ansId = i;
                ansAvg = avg;
            }
        }
        if (ansId == -1)
            return "No Solution";
        else {
            return "G" + (ansId - N)+"\t"+String.format("%.1f %.1f", ansDis, ansAvg);
        }
    }

    static void Dijkstra(int s) {
        Arrays.fill(d, INF);
        Arrays.fill(vis, false);
        d[s] = 0;
        for (int i = 0; i < N + M; i++) {
            int u = -1, MIN = INF;
            for (int j = 1; j <= N + M; j++) {
                if (!vis[j] && d[j] < MIN) {
                    u = j;
                    MIN = d[j];
                }
            }
            if (u == -1) return;
            vis[u] = true;
            for (int v = 1; v <= N + M; v++) {
                if (!vis[v] && G[u][v] != INF && d[u] + G[u][v] < d[v]) {
                    d[v] = d[u] + G[u][v];
                }
            }
        }
    }
    static {
        int count =1000;
        Random random=new Random();
        while (count-- > 0) {
            int n = random.nextInt(10) + 1;
            int m = random.nextInt(3) + 1;
            int k=random.nextInt(30)+1;
            int limit=random.nextInt(100)+1;
            Set<String> set=new HashSet<>();
            List<String> src=new ArrayList<>();
            List<String> target=new ArrayList<>();
            List<Integer> weight=new ArrayList<>();
            while (set.size()<n+m){
                String s=random.nextBoolean()?("G"+(random.nextInt(m)+1)):(random.nextInt(n)+1+"");
                String t=random.nextBoolean()?("G"+(random.nextInt(m)+1)):(random.nextInt(n)+1+"");
                src.add(s);
                target.add(t);
                weight.add(random.nextInt(100)+1);
                set.add(s);
                set.add(t);
            }
            int size = src.size();
            String []src1=new String[size];
            String []target1=new String[size];
            Integer []weight1=new Integer[size];
            src.toArray(src1);
            target.toArray(target1);
            weight.toArray(weight1);
            String fun = fun(n, m, size, limit, src1, target1, weight1);
            T14.Graph graph = new T14.Graph(src1, target1, weight1,n);
            String myFun = T14.fun(graph, n, m, limit);
            if (!fun.equals(myFun)){
                System.out.println("预期："+fun);
                System.out.println("实际："+myFun);
                System.out.println("n:"+n+"\tm:"+m+"\tlimit:"+limit);
                System.out.println(src.toString());
                System.out.println(target.toString());
                System.out.println(weight.toString());
            }
        }
    }

    public static void main(String[] args) {

    }
}
